<!DOCTYPE html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Java HashMap 工作机制详解</title>
    <link href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css" rel="stylesheet">
    <link href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css" rel="stylesheet">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
            color: #333;
            line-height: 1.6;
        }
        .hero {
            background: linear-gradient(135deg, #6e8efb 0%, #a777e3 100%);
        }
        .section-title {
            position: relative;
            padding-left: 1.5rem;
        }
        .section-title:before {
            content: '';
            position: absolute;
            left: 0;
            top: 0.5rem;
            height: 1.5rem;
            width: 0.5rem;
            background: linear-gradient(to bottom, #6e8efb, #a777e3);
            border-radius: 0.25rem;
        }
        .card {
            transition: all 0.3s ease;
            box-shadow: 0 4px 6px rgba(0, 0, 0, 0.05);
        }
        .card:hover {
            transform: translateY(-5px);
            box-shadow: 0 10px 15px rgba(0, 0, 0, 0.1);
        }
        .code-block {
            background: #f8f8f8;
            border-left: 4px solid #6e8efb;
        }
        .highlight {
            background-color: rgba(110, 142, 251, 0.1);
            padding: 0.2rem 0.4rem;
            border-radius: 0.25rem;
        }
        .list-item {
            position: relative;
            padding-left: 1.5rem;
        }
        .list-item:before {
            content: '•';
            position: absolute;
            left: 0.5rem;
            color: #6e8efb;
            font-weight: bold;
        }
        .mermaid {
            background: white;
            padding: 1rem;
            border-radius: 0.5rem;
            box-shadow: 0 4px 6px rgba(0, 0, 0, 0.05);
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero text-white py-20 px-4 md:px-0">
        <div class="container mx-auto max-w-5xl">
            <div class="flex flex-col items-center text-center">
                <h1 class="text-4xl md:text-5xl font-bold mb-4 font-serif">深入解析 Java HashMap</h1>
                <p class="text-xl md:text-2xl mb-8 max-w-3xl">探索哈希冲突处理机制与现代 Java 集合框架的高效实现</p>
                <div class="flex space-x-4">
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full"><i class="fas fa-code mr-2"></i>Java 集合框架</span>
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full"><i class="fas fa-project-diagram mr-2"></i>哈希算法</span>
                    <span class="px-4 py-2 bg-white bg-opacity-20 rounded-full"><i class="fas fa-tachometer-alt mr-2"></i>性能优化</span>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="container mx-auto max-w-5xl px-4 md:px-0 py-12">
        <!-- Introduction -->
        <section class="mb-16">
            <div class="bg-white rounded-xl p-8 shadow-md">
                <p class="text-lg leading-relaxed text-gray-700">
                    <span class="text-3xl font-bold text-gray-800 float-left mr-2 -mt-1">在</span>
                    Java 中，<span class="highlight">HashMap</span> 是通过哈希值来确定键值对存储位置的。当两个对象的 <span class="highlight">hashCode()</span> 返回值相等时，<span class="highlight">HashMap</span> 会将它们存储在同一个桶（bucket）中，发生了哈希冲突（collision）。但即使 <span class="highlight">hashCode</span> 相等，这两个对象也不一定是相等的。
                </p>
            </div>
        </section>

        <!-- Section 1 -->
        <section class="mb-16">
            <h2 class="section-title text-2xl font-bold mb-6">1. 计算哈希值和定位桶</h2>
            <div class="grid md:grid-cols-2 gap-8">
                <div class="card bg-white rounded-xl p-6">
                    <p class="text-gray-700 mb-4">
                        当将键值对插入 <span class="highlight">HashMap</span> 时，首先会根据键的 <span class="highlight">hashCode()</span> 计算出一个哈希值。这个哈希值决定了键值对在哈希表中存储的桶位置。具体地，<span class="highlight">HashMap</span> 使用哈希值和桶数组的长度来计算存储位置，公式为：
                    </p>
                    <div class="code-block p-4 rounded mb-4 overflow-x-auto">
                        <code class="text-sm text-gray-800">index = (n - 1) & hash</code>
                    </div>
                    <p class="text-gray-700">
                        其中，<span class="highlight">n</span> 是桶数组的长度，<span class="highlight">hash</span> 是经过扰动函数计算后的哈希值。
                    </p>
                </div>
                <div class="card bg-white rounded-xl p-6 flex items-center justify-center">
                    <div class="mermaid">
                        graph LR
                            A[键对象] --> B[计算hashCode()]
                            B --> C[扰动函数处理]
                            C --> D[计算桶位置]
                            D --> E[index = (n-1) & hash]
                    </div>
                </div>
            </div>
        </section>

        <!-- Section 2 -->
        <section class="mb-16">
            <h2 class="section-title text-2xl font-bold mb-6">2. 处理哈希冲突</h2>
            <div class="card bg-white rounded-xl p-6 mb-8">
                <p class="text-gray-700">
                    当两个键的哈希值相等，且它们被映射到相同的桶位置时，就会发生哈希冲突。<span class="highlight">HashMap</span> 使用以下方法来处理这种情况：
                </p>
            </div>

            <div class="grid md:grid-cols-2 gap-8">
                <div class="card bg-white rounded-xl p-6">
                    <h3 class="text-xl font-bold mb-4 text-indigo-600">2.1 链表结构</h3>
                    <p class="text-gray-700">
                        在 JDK 8 之前，如果两个键被映射到同一个桶，<span class="highlight">HashMap</span> 会将这些键值对以链表的形式存储在这个桶中。新的键值对会根据链表的插入方式（JDK 8 之前是头插法，JDK 8 之后是尾插法）插入到链表中。
                    </p>
                </div>

                <div class="card bg-white rounded-xl p-6">
                    <h3 class="text-xl font-bold mb-4 text-indigo-600">2.2 红黑树结构</h3>
                    <p class="text-gray-700">
                        从 JDK 8 开始，当链表的长度超过一定阈值（默认是 8）时，链表会自动转换为红黑树（Red-Black Tree）。红黑树是一种自平衡二叉搜索树，其查找、插入和删除操作的时间复杂度为 O(log n)，比链表的 O(n) 要高效得多。
                    </p>
                </div>
            </div>
        </section>

        <!-- Visualization Section -->
        <section class="mb-16">
            <div class="card bg-white rounded-xl p-6">
                <div class="mermaid">
                    graph TD
                        A[HashMap桶数组] --> B[桶0]
                        A --> C[桶1]
                        A --> D[...]
                        A --> E[桶n]
                        
                        B --> F[链表节点1]
                        F --> G[链表节点2]
                        G --> H[链表节点3]
                        
                        C --> I[红黑树根节点]
                        I --> J[左子节点]
                        I --> K[右子节点]
                        J --> L[...]
                        K --> M[...]
                </div>
            </div>
        </section>

        <!-- Section 3 -->
        <section class="mb-16">
            <h2 class="section-title text-2xl font-bold mb-6">3. 比较对象的相等性</h2>
            <div class="card bg-white rounded-xl p-6">
                <p class="text-gray-700 mb-4">
                    即使两个对象的 <span class="highlight">hashCode</span> 相等，<span class="highlight">HashMap</span> 也不能直接认定它们是相同的对象。在插入新键值对时，<span class="highlight">HashMap</span> 会遍历链表或红黑树结构，逐一使用 <span class="highlight">equals()</span> 方法比较新键和已存在键的相等性：
                </p>
                <ul class="space-y-2">
                    <li class="list-item">
                        <span class="font-bold">如果 <span class="highlight">equals()</span> 返回 <span class="highlight">true</span>：</span>说明新键与已存在键是相同的对象，此时，<span class="highlight">HashMap</span> 会认为这是一个重复的键，会更新其对应的值为新值，替换掉旧的值。
                    </li>
                    <li class="list-item">
                        <span class="font-bold">如果 <span class="highlight">equals()</span> 返回 <span class="highlight">false</span>：</span>说明新键和已存在键是不同的对象，<span class="highlight">HashMap</span> 会将新键值对作为新的节点添加到链表或红黑树中。
                    </li>
                </ul>
            </div>
        </section>

        <!-- Section 4 -->
        <section class="mb-16">
            <h2 class="section-title text-2xl font-bold mb-6">4. 插入后的结构</h2>
            <div class="grid md:grid-cols-2 gap-8">
                <div class="card bg-white rounded-xl p-6">
                    <h3 class="text-xl font-bold mb-4 text-indigo-600">链表结构</h3>
                    <p class="text-gray-700">
                        如果桶内仍然是链表结构，新的键值对会被添加到链表的尾部。
                    </p>
                    <div class="mt-4 flex justify-center">
                        <i class="fas fa-link text-3xl text-indigo-500"></i>
                        <i class="fas fa-arrow-right mx-4 text-gray-400 mt-2"></i>
                        <i class="fas fa-link text-3xl text-indigo-500"></i>
                        <i class="fas fa-arrow-right mx-4 text-gray-400 mt-2"></i>
                        <i class="fas fa-link text-3xl text-indigo-500"></i>
                        <i class="fas fa-arrow-right mx-4 text-gray-400 mt-2"></i>
                        <i class="fas fa-plus-circle text-3xl text-green-500"></i>
                    </div>
                </div>
                <div class="card bg-white rounded-xl p-6">
                    <h3 class="text-xl font-bold mb-4 text-indigo-600">红黑树结构</h3>
                    <p class="text-gray-700">
                        如果桶内是红黑树结构，新的键值对会根据红黑树的性质插入到合适的位置，保持树的平衡性。
                    </p>
                    <div class="mt-4 flex justify-center">
                        <i class="fas fa-tree text-3xl text-green-600"></i>
                        <div class="ml-4">
                            <div class="flex">
                                <i class="fas fa-leaf text-xl text-green-500 mr-2"></i>
                                <i class="fas fa-leaf text-xl text-green-500"></i>
                            </div>
                            <div class="flex mt-1">
                                <i class="fas fa-leaf text-xl text-green-500 mr-1"></i>
                                <i class="fas fa-plus-circle text-lg text-white bg-green-500 rounded-full p-1"></i>
                                <i class="fas fa-leaf text-xl text-green-500 ml-1"></i>
                            </div>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Section 5 -->
        <section class="mb-16">
            <h2 class="section-title text-2xl font-bold mb-6">5. 查询操作</h2>
            <div class="card bg-white rounded-xl p-6">
                <p class="text-gray-700">
                    在执行查询操作时，<span class="highlight">HashMap</span> 首先会根据键的 <span class="highlight">hashCode</span> 找到对应的桶，然后遍历桶内的链表或红黑树，依次调用 <span class="highlight">equals()</span> 方法来查找与查询键匹配的键值对。如果找到匹配的键，则返回对应的值；如果遍历结束仍未找到匹配项，则返回 <span class="highlight">null</span>，表示没有找到对应的键值对。
                </p>
                <div class="mt-6 mermaid">
                    graph LR
                        A[查询键] --> B[计算hashCode]
                        B --> C[定位桶位置]
                        C --> D{桶结构类型}
                        D -->|链表| E[顺序遍历链表查找]
                        D -->|红黑树| F[树遍历查找]
                        E --> G[equals匹配?]
                        F --> G
                        G -->|是| H[返回对应值]
                        G -->|否| I[返回null]
                </div>
            </div>
        </section>

        <!-- Summary Section -->
        <section class="mb-16">
            <div class="bg-gradient-to-r from-indigo-50 to-purple-50 rounded-xl p-8">
                <h2 class="text-2xl font-bold mb-4 text-indigo-800">关键要点总结</h2>
                <ul class="grid md:grid-cols-2 gap-4">
                    <li class="flex items-start">
                        <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                        <span>HashMap 使用哈希值确定键值对存储位置</span>
                    </li>
                    <li class="flex items-start">
                        <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                        <span>哈希冲突通过链表或红黑树解决</span>
                    </li>
                    <li class="flex items-start">
                        <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                        <span>JDK 8 引入红黑树优化长链表性能</span>
                    </li>
                    <li class="flex items-start">
                        <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                        <span>equals() 方法决定键的实际相等性</span>
                    </li>
                    <li class="flex items-start">
                        <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                        <span>查询时先定位桶，再遍历结构查找</span>
                    </li>
                    <li class="flex items-start">
                        <i class="fas fa-check-circle text-green-500 mt-1 mr-2"></i>
                        <span>良好的 hashCode() 实现可减少冲突</span>
                    </li>
                </ul>
            </div>
        </section>
    </main>

    <!-- Footer -->
    <footer class="bg-gray-900 text-gray-300 py-8">
        <div class="container mx-auto max-w-5xl px-4 md:px-0">
            <div class="flex flex-col md:flex-row justify-between items-center">
                <div class="mb-4 md:mb-0">
                    <h3 class="text-xl font-bold text-white">技术小馆</h3>
                    <p class="text-gray-400">探索技术之美，分享编程之道</p>
                </div>
                <div>
                    <a href="http://www.yuque.com/jtostring" class="text-gray-300 hover:text-white transition-colors duration-300">
                        <i class="fas fa-globe mr-2"></i>http://www.yuque.com/jtostring
                    </a>
                </div>
            </div>
        </div>
    </footer>

    <script>
        mermaid.initialize({
            startOnLoad: true,
            theme: 'default',
            flowchart: {
                useMaxWidth: true,
                htmlLabels: true,
                curve: 'basis'
            }
        });
    </script>
</body>
</html>